22_eficiencia_de_hashing_y_factor_de

Definición del Factor de Carga ($\lambda$)

El Factor de Carga ($\lambda$)es la métrica principal que determina la eficiencia en el mundo real de una tabla hash. Cuantifica cuán llena está la tabla, correlacionándose directamente con la probabilidad y la longitud de las colisiones.

$$ \lambda = \frac{\text{Número de elementos almacenados } (N)}{\text{Tamaño de la tabla/cubetas } (M)} $$

Encadenamiento Separado: $\lambda$ representa la longitud promediode las listas enlazadas (cadenas).
Dirección Abierta (Exploración): $\lambda$ representa la saturación de la tabla, correlacionándose directamente con el número esperado de exploracionesnecesarias para encontrar un espacio vacío o un elemento específico.

Factor de Carga y Complejidad

Para lograr el rendimiento teórico de $O(1)$en el caso promedio para operaciones de Búsqueda, Inserción y Eliminación, el Factor de Carga ($\lambda$) debe ser constante y generalmente pequeño (por ejemplo, $< 1.0$ o $< 0.75$).

Factor de Rendimiento	Caso Promedio (Valor objetivo de $\lambda$)	Peor Caso (Alto $\lambda$)
Tiempo de Búsqueda/Inserción	$O(1 + \lambda) \approx O(1)$	$O(N)$ (Se aproxima a búsqueda lineal)
Tasa de Colisiones	Baja/Gestionable	Alta
Sobrecarga de Espacio	$O(N + M)$	$O(N + M)$

Implicación clave:Si $M$ es fijo y $N$ crece, $\lambda$ aumenta, deteriorando el rendimiento hacia $O(N)$.

Estrategia: Gestión de Saturación (Rehashing)

Para prevenir la degradación de rendimiento causada por un alto $\lambda$, las tablas hash eficientes implementan Rehashing (redimensionamiento).

Monitoreo de Límite: El sistema monitorea $\lambda$. Si excede un umbral predefinido (por ejemplo, 0.75 para Dirección Abierta, o 2.0 para Encadenamiento), se activa la redimensionamiento.
Expansión: El tamaño de la tabla $M$ se incrementa (por ejemplo, duplicado a $M'$).
Redistribución: Todos los $N$ elementos existentes se vuelven a insertar en la nueva tabla más grande $M'$, utilizando posiblemente una función hash nueva (módulo $M'$).

Resultado: $\lambda$ disminuye inmediatamente, restaurando la garantía de rendimiento promedio de la estructura $O(1)$de rendimiento promedio. Tenga en cuenta que la operación de rehashing en sí misma tiene un costo temporal de $O(N)$.

📝 Cuestionario Interactivo

1. ¿Cuál es el propósito principal del rehashing de una tabla hash?

A) Ordenar los elementos dentro de la tabla.
B) Reducir el factor de carga y mantener un rendimiento promedio de $O(1)$.
C) Liberar inmediatamente los espacios de memoria no utilizados.
D) Verificar posibles corrupciones de datos.

2. En una tabla hash que utiliza Encadenamiento Separado, si $N=20$ elementos están almacenados en $M=10$ cubetas, ¿qué representa el factor de carga $\lambda=2$?

A) La tabla está completamente llena y no puede aceptar nuevos elementos.
B) El tiempo de búsqueda en el peor caso es exactamente 2 comparaciones.
C) La longitud promedio de las listas enlazadas (cadenas) es 2.
D) Al menos una cubeta debe contener exactamente 2 elementos.

3. Un sistema utiliza una tabla hash con Dirección Abiertacon $M=10,000$ ranuras. Almacena $N=1,500$ elementos. ¿Cuál es la complejidad de tiempo promedio esperada para una búsqueda?

A) $O(1)$
B) $O(\log N)$
C) $O(N)$
D) $O(\lambda)$

4. Aunque una sola operación de rehashing cuesta $O(N)$, ¿por qué el costo amortizadodel insertar aún se considera $O(1)$?

A) El alto costo es poco frecuente y se distribuye sobre muchas inserciones baratas.
B) El rehashing solo ocurre cuando la tabla está vacía.
C) El costo $O(N)$ es un máximo teórico que nunca ocurre realmente.
D) Las CPU modernas pueden realizar el rehash en un único ciclo de reloj.